package com.leetcode;

import java.util.*;

/**
 * 1606. 找到处理最多请求的服务器
 *
 * @author fy
 * @date 2022/3/30 17:39
 */
public class Solution1606 {

    public class Node {
        public int num;
        public int endTime;
    }

    public List<Integer> busiestServers(int k, int[] arrival, int[] load) {
        TreeSet<Integer> available = new TreeSet<>();
        for (int i = 0; i < k; i++) {
            available.add(i);
        }
        int[] count = new int[k];
        PriorityQueue<Node> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(p -> p.endTime));
        for (int i = 0; i < arrival.length; i++) {
            while (!priorityQueue.isEmpty() && priorityQueue.peek().endTime <= arrival[i]) {
                available.add(priorityQueue.poll().num);
            }
            if (available.isEmpty()) {
                continue;
            }

            Integer num = available.ceiling(i % k);
            if (num == null) {
                num = available.first();
            }
            Node newNode = new Node();
            newNode.num = num;
            newNode.endTime = arrival[i] + load[i];
            count[num]++;
            available.remove(num);
            priorityQueue.offer(newNode);
        }
        int max = Arrays.stream(count).max().getAsInt();
        // List<Integer> list = Arrays.stream(count).filter(item -> item == max).boxed().collect(Collectors.toList());
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            if (count[i] == max) {
                list.add(i);
            }
        }
        return list;
    }

    public static void main(String[] args) {
        int k = 3;
        int[] arrival = new int[]{1, 2, 3, 4, 5};
        int[] load = new int[]{5, 2, 3, 3, 3};
        System.out.println(new Solution1606().busiestServers(k, arrival, load));
    }

}
